home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / share / python-support / python-rdflib / rdflib / sparql / bison / CompositionalEvaluation.py < prev    next >
Encoding:
Python Source  |  2007-04-04  |  4.6 KB  |  121 lines
  1. """
  2. This module implements (with sparql-p) compositional forms and semantics as outlined in
  3. the pair of Jorge P¬¥erez et. al papers:
  4.  
  5. - Semantics of SPARQL                (http://ing.utalca.cl/~jperez/papers/sparql_semantics.pdf)
  6. - Semantics and Complexity of SPARQL (http://arxiv.org/abs/cs.DB/0605124)
  7.  
  8. It also implements rewrite rules expressed in the SPARQL Algebra:
  9.  
  10. - http://www.w3.org/TR/rdf-sparql-query/#sparqlAlgebra
  11.  
  12. Compositional Semantics (Jorge P. et. al syntax)
  13.  
  14. == Definition 3.7 (Set of Mappings and Operations) ==
  15.  
  16. Omega1 and Omega2 are sets of mappings
  17.  
  18. I.   Omega1 ‚ãâ Omega2          = {Œº1 ‚à™ Œº2 | Œº1 ‚àà Omega1, Œº2 ‚àà Omega2 are compatible mappings } 
  19. II.  Omega1 ‚à™ Omega2           = {Œº | Œº1 ‚àà Omega1 or Œº2 ‚àà Omega2 }
  20. III. Omega1 \ Omega2           = {Œº1 ‚àà Omega1 | for all Œº‚Ä≤ ‚àà Omega2, Œº and Œº‚Ä≤ are not compatible }
  21. IV.  LeftJoin1(Omega1, Omega2) = ( Omega1 ‚ãâ Omega2 ) ‚à™ ( Omega1 \ Omega2 ) 
  22.  
  23. NOTE: sparql-p implements the notion of compatible mappings with the 'clash' attribute
  24. defined on instances of _SPARQLNode (in the evaluation expansion tree)   
  25.  
  26. An RDF dataset is a set D = {G0, <u1,G1>,... <un,Gn>}
  27.  
  28. where G0, . . . ,Gn are RDF graphs, u1, . . . , un are IRIs, and n ‚â• 0.
  29.  
  30. NOTE: A SPARQL RDF dataset is equivalent to an RDFLib ConjunctiveGraph so we introduce
  31. a function rdflibDS(D) which returns the ConjunctiveGraph instance associated
  32. with the dataset D
  33.  
  34. Every dataset D is equipped with a function dD such that
  35. dD(u) = G if u,Gi ‚àà D and dD(u) = ‚àÖ otherwise
  36.  
  37. Let D be an RDF dataset and G an RDF graph in D
  38.  
  39. == Definition 3.9 (Graph Pattern Evaluation): ==
  40.  
  41. [[.]](D,G) Is the notation used to indicate the evaluation
  42. of a graph pattern.  
  43.  
  44. I.  [[(P1 AND P2)]](D,G)   = [[P1]](D,G) ‚ãâ [[P2]](D,G)
  45. II. [[(P1 UNION P2)]](D,G) = [[P1]](D,G) ‚à™ [[P2]](D,G)
  46. III.[[(P1 OPT P2)]](D,G)   = LeftJoin1([[P1]](D,G),[[P2]](D,G))  
  47. IV. If u ‚àà I, then 
  48.       [[(u GRAPH P)]](D,G)  = [[P]](D,dD(u))
  49.     if ?X ‚àà V , then
  50.       [[(?X GRAPH P)]](D,G) =
  51.         [[P]](D,G) ‚ãâ { ?X -> rdflibDS(D).contexts(P) }
  52. V. [[(P FILTER R)]](D,G) = {Œº ‚àà [[P]](D,G) | Œº |= R}.
  53.  
  54. NOTE: RDFLib's ConjunctiveGraph.contexts method is used to append bindings
  55. for GRAPH variables.  The FILTER semantics are implemented 'natively'
  56. in sparql-p by python functions 
  57.  
  58. (http://dev.w3.org/cvsweb/2004/PythonLib-IH/Doc/sparqlDesc.html?rev=1.11#Constraini)
  59.  
  60. == Equivalence with SPARQL  Algebra (*from* DAWG SPARQL Algebra *to* Jorge.P et. al forms) ==
  61.  
  62. merge(Œº1,Œº2)             = Œº1 ‚à™ Œº2
  63. Join(Omega1,Omega2)      = Filter(R,Omega1 ‚ãâ Omega2)
  64. Filter(R,Omega)          = [[(P FILTER R)]](D,G)
  65. Diff(Omega1,Omega2,R)    = (Omega1 \ Omega2) ‚à™ {Œº | Œº in Omega1 ‚ãâ Omega2 and *not* Œº |= R} 
  66. Union(Omega1,Omega2)     = Omega1 ‚à™ Omega2 
  67.  
  68. #LeftJoin(Omega1,Omega2,R)= Filter(R,Join(Omega1,Omega2)) ‚à™ Diff(Omega1,Omega2,R)
  69.  
  70. == Graph Pattern rewrites and reductions ==
  71.  
  72. [[{t1, t2, . . . , tn}]]D = [[({t1} AND {t2} AND ¬∑ ¬∑ ¬∑ AND {tn})]]D
  73.  
  74. Proposition 3.13
  75.  
  76. The above proposition implies that it is equivalent to consider basic
  77. graph patterns or triple patterns as the base case when defining SPARQL general graph patterns.    
  78.  
  79. == BGP reduction and Disjunctive Normal Forms or Union-Free BGP ==
  80.  
  81. Step 5 of http://www.w3.org/TR/rdf-sparql-query/#convertGraphPattern
  82.     
  83. Replace Join({}, A) by A
  84. Replace Join(A, {}) by A
  85.  
  86. === Disjunctive Normal Form of SPARQL Patterns ==
  87.  
  88. See: http://en.wikipedia.org/wiki/Disjunctive_normal_form
  89.  
  90. From Proposition 1 of 'Semantics and Complexity of SPARQL'
  91.  
  92. I.  (P1 AND (P2 UNION P3)) ‚â° ((P1 AND P2) UNION (P1 AND P3))
  93. II. (P1 OPT (P2 UNION P3)) ‚â° ((P1 OPT P2) UNION (P1 OPT P3))
  94. III.((P1 UNION P2) OPT P3) ‚â° ((P1 OPT P3) UNION (P2 OPT P3)) 
  95. IV. ((P1 UNION P2) FILTER R) ‚â° ((P1 FILTER R) UNION (P2 FILTER R)) 
  96.  
  97. The application of the above equivalences permits to translate any graph pattern
  98. into an equivalent one of the form:
  99.  
  100. P1 UNION P2 UNION P3 UNION ... UNION P
  101.  
  102. NOTE: sprarql-p SPARQL.query API is geared for evaluation of SPARQL patterns already in DNF:
  103.  - http://dev.w3.org/cvsweb/~checkout~/2004/PythonLib-IH/Doc/Attic/pythondoc-sparql.html?rev=1.5&content-type=text/html;%20charset=iso-8859-1#sparql.SPARQL.query-method
  104.  
  105. """
  106.  
  107. def ReduceToDNF(ggp,prolog):
  108.     """
  109.     From: Semantics of SPARQL
  110.     
  111.     [[{t1, t2, . . . , tn}]]D = [[({t1} AND {t2} AND ¬∑ ¬∑ ¬∑ AND {tn})]]D
  112.     
  113.     Proposition 3.13
  114.     
  115.     The above proposition implies that it is equivalent to consider basic
  116.     graph patterns or triple patterns as the base case when defining SPARQL general graph patterns.    
  117.     """
  118.     pass
  119.  
  120. def CompositionalEvaluate(tripleStore,ggp,prolog,passedBindings):
  121.     pass